import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 邻接表
 * 使用链表来实现图
 * 链表头代表的是开始节点，后面的节点表示的是和链表连接的边
 */
public class nodeGraph {
    static class node {
        int val;
        int weight;
        node next;

        public node(int val) {
            this.val = val;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

    boolean isDirect;
    private ArrayList<node> nodes;//储存头节点，也就是边的开始
    private char[] charV;

    public nodeGraph(int size, boolean isDirect) {
        this.isDirect = isDirect;
        nodes = new ArrayList<>(size);
        charV = new char[size];
    }

    public void initV(char[] chars) {
        //初始化字符节点
        for (int i = 0; i < chars.length; i++) {
            this.charV[i] = chars[i];
        }
        //初始化头节点
        for (int i = 0; i < chars.length; i++) {
            nodes.add(new node(chars[i]));
        }
    }

    //得到对应的起始位置节点
    public int getStrIndex(char c) {
        for (int i = 0; i < charV.length; i++) {
            if (charV[i] == c) {
                return i;
            }
        }
        return -1;
    }

    //插入边
    public boolean addEdge(char str, char end, int weight) {
        int strIndex = getStrIndex(str);//其实边对应的位置
        int endIndex = getStrIndex(end);//终点边对应的位置
        if (strIndex == -1 || endIndex == -1) {
            return false;
        }
        node prev = null;
        node cur = nodes.get(strIndex);

        while (cur != null) {
            if (cur.val == endIndex) {//说明这条边已经插入过了
                return false;
            }
            prev = cur;
            cur = cur.next;
        }
        //这时将prev连接其终点就好
        prev.next = new node(endIndex);
        prev.next.setWeight(weight);

        if (!isDirect) {//是无向的那么就要在插入
            addEdge(end, str, weight);
        }
        return true;
    }

    public void showEdge() {
        for (int i = 0; i < nodes.size(); i++) {
            node tmpNode = nodes.get(i);
            tmpNode = tmpNode.next;
            while (tmpNode != null) {
                System.out.print(charV[i] + " -> ");
                System.out.print(charV[tmpNode.val] + "    ");
                tmpNode = tmpNode.next;
            }
            System.out.println();
        }
    }

    /**
     * 获得对应点的度
     * 顶点的度指的是该点的入度和出度
     */
    public int getDevV(char c) {
        int sIndex = getStrIndex(c);
        int count = 0;
        if (!isDirect) {//如果是无向的 遍历链表就好
            node cur = nodes.get(sIndex);
            cur = cur.next;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count * 2;
        } else {//有向的，要遍历所有链表
            for (int i = 0; i < nodes.size(); i++) {
                if (charV[i] == c) {//顶点等于c
                    node cur = nodes.get(i);
                    cur = cur.next;
                    while (cur != null) {
                        count++;
                        cur = cur.next;

                    }
                } else {//遍历链表找到的终点为c的
                    node cur = nodes.get(i);
                    cur = cur.next;
                    while (cur != null) {
                        if (charV[cur.val] == c) {
                            count ++;
                        }
                        cur = cur.next;
                    }
                }
            }
            return count;
        }
    }


    public static void main(String[] args) {
        nodeGraph m = new nodeGraph(4, false);
        char[] chars = {'A', 'B', 'C', 'D'};
        m.initV(chars);
        m.addEdge('A', 'B', 1);
        m.addEdge('A', 'D', 1);
        m.addEdge('B', 'A', 1);
        m.addEdge('B', 'C', 1);
        m.addEdge('D', 'A', 1);
        m.addEdge('D', 'C', 1);
//        m.showMatrix();
//        m.showEdge();
        System.out.println(m.getDevV('C'));
        System.out.println("stop");
    }
}
